// 189. 轮转数组
// 提示
// 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 

// 示例 1:

// 输入: nums = [1,2,3,4,5,6,7], k = 3
// 输出: [5,6,7,1,2,3,4]
// 解释:
// 向右轮转 1 步: [7,1,2,3,4,5,6]
// 向右轮转 2 步: [6,7,1,2,3,4,5]
// 向右轮转 3 步: [5,6,7,1,2,3,4]
// 示例 2:

// 输入：nums = [-1,-100,3,99], k = 2
// 输出：[3,99,-1,-100]
// 解释: 
// 向右轮转 1 步: [99,-1,-100,3]
// 向右轮转 2 步: [3,99,-1,-100]
 

// 提示：

// 1 <= nums.length <= 105
// -231 <= nums[i] <= 231 - 1
// 0 <= k <= 105
 

// 进阶：

// 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
// 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const n = nums.length;
    k %= n;
    if (!k) return ;


    // 1 创建额外数组，利用规则完成轮转
    // 1.1 利用映射关系重新排列nums
    // let copy = [...nums];

    // for(let i = 0; i < nums.length; i ++) {
    //     nums[(i + k) % n] = copy[i]
    // }


    // 1.2 遍历n-k之后的数据，以及0~k的数据，重新排列nums
    // const copy = [...nums];
    // for(let i = 0; i < k; i ++) {
    //     nums[i] = copy[n - k + i]
    // };
    // for(let i = k; i < n; i ++) {
    //     nums[i] = copy[i - k]
    // }

    // // 2. 数组翻转
    // const reverse = (nums, start, end) => {
    //     while(start < end) {
    //         const temp = nums[start];
    //         nums[start] = nums[end];
    //         nums[end] = temp;
    //         start ++;
    //         end --;
    //     }
    // }
    // reverse(nums, 0, n - 1);
    // reverse(nums, 0, k - 1);
    // reverse(nums, k, n - 1);

    // // 3. 环状替换
    // const gcd = (x, y) => y ? gcd(y, x % y) : x;

    // let count = gcd(k, n);
    // for (let start = 0; start < count; ++start) {
    //     let current = start;
    //     let prev = nums[start];
    //     do {
    //         const next = (current + k) % n;
    //         const temp = nums[next];
    //         nums[next] = prev;
    //         prev = temp;
    //         current = next;
    //     } while (start !== current);
    // }
    
};